% two stations are neighbours if they are connected
neighbour(X, Y, L):- edge(Y, X, L) ; edge(X, Y, L). 			% required as edges are only unidirectional

% find a path between two stations
path(X, Y, [X], Visited):- X=:=Y.									% Case when start and end stations are the same
path(X, Y, [X, Y], Visited):- X=\=Y, neighbour(X, Y, _), !. % X and Y are neighbouring stations, so there is a path
path(X, Y, [X|P2], Visited):-
	X=\=Y,
	neighbour(X, Z, _), 													% there's another stations neighbouring of X
	not member(Z, Visited), 											% which hasn't been visited
	path(Z, Y, P2, [X|Visited]). 										% try to find a path connecting Z and Y.

% calculate the length of the path ( the time taken )
length([X], -3). 															% To and From the same station, no time needed.
length([X|T], L):- transfer([X|T], L, R). 						% Find the time when there is a path

% additional time when changing train line
transfer([X, Y], 2, R):- check(X,Y,R,R), !. 						% For two neighbouring stations, time taken is 2 minutes
transfer([X,Y|T], L, R):- 
	transfer([Y|T], L2,R2), 											% recursive rule for remaining stations first
	check(X,Y,R, R2), !, 												% check current train line and next train line
	different(R, R2, TL), 												% get any additional time for train line transfer
	L is L2+TL+2. 															% return the time for traveling and train line transfer

% check and get the current line between 2 station
% additional cases to cover stations that are connected in more than one line
check(X,Y,R,R):- X =:= "Raffles Place", Y=:= "City Hall".
check(X,Y,R,R):- X =:= "City Hall", Y=:= "Raffles Place".
check(X,Y,R,_):- neighbour(X,Y,R).

% compare previous line and current line and return additional time if any
% eg. transferring from EW line to CC line will take an additional 5 minutes
different(R1, R2, 0):- var(R2).
different(R1, R2, 0):- not var(R2), R1 =:= R2.
different(R1, R2, 5):- not var(R2), R1 =\= R2.

% compare total path length and return the smaller one
smaller(A, B, AP, BP, BP, B):- A >= B.
smaller(A, B, AP, BP, AP, A):- A < B.

% compare the different paths and find the shortest path among all
shortest_path([A], A, B):- length(A, B). 							% only 1 path, so find the length of this path
shortest_path([A|T], BP, Z):-
	length(A, Z2), 														% get the length for the first path
	shortest_path(T, BP2, Z3),											% get the shortest path from remaining paths 
	smaller(Z2, Z3, A, BP2, BP, Z). 									% get the shorter path as Z

% find the path and time needed between 2 station
find_distance(X, Y, BP, Z):-
	findall(P, path(X, Y, P, []), A), 								% find all possible paths
	shortest_path(A, BP, Z2), 											% and get the shortest path among them
	Z is Z2 + 3. 															% add the travel time + initial waiting time of 3 minutes